import json

class BinaryNode:
    def __init__(self,value,left=None,right=None) -> None:
        """
        默认构造 BinaryNode(value,left,right)
        通过字典构造 BinaryNode(dict)
        通过json字符串构造 BinaryNode(str)
        """
        if isinstance(value,dict) and left is None:
            node = dict2tree(value)
            self.value = node.value
            self.left = node.left
            self.right = node.right
        elif isinstance(value,str) and left is None:
            node = dict2tree(json.loads(value))
            self.value = node.value
            self.left = node.left
            self.right = node.right
        else:
            self.value = value
            self.left = left
            self.right = right
            self.result = None

    def to_dict(self):
        """
        将树转换为字典
        """
        return tree2dict(self)

    def __iter__(self):
        stack = []
        flag_stack = [] #左支返回为0 右支返回为1
        current = self
        while stack or current is not None:
            while current is not None and isinstance(current,BinaryNode):
                stack.append(current)
                flag_stack.append(0)
                current = current.left
            current = stack.pop()
            flag = flag_stack.pop()
            if flag == 0:
                stack.append(current)
                flag_stack.append(1)
                current = current.right
            else:
                yield current
                current = None


def dict2tree(t)->BinaryNode:
    b = BinaryNode(t['value'],
                    dict2tree(t['left']) if type(t['left']) is dict else t['left'],
                    dict2tree(t['right']) if type(t['right']) is dict else t['right']) 
    return b           

def tree2dict(node)->dict:
    t = {'value':node.value,
         'left':tree2dict(node.left) if isinstance(node.left,BinaryNode) else node.left,
         'right':tree2dict(node.right) if isinstance(node.right,BinaryNode) else node.right
         }
    return t